package leetcode.code1140;

/**
 * @author CaoYu
 * @date 2021年10月5日
 * @description
 */
public class Solution extends Solution1140 {

	@Override
	public int stoneGameII(int[] piles) {
		int len = piles.length;
		int[] pre = new int[len + 1];
		for (int i = 0; i < len; i++) {
			pre[i + 1] = piles[i] + pre[i];
		}
		int m = 1;
		Integer[][] dp = new Integer[len][len + 1];
		return stoneGameII(pre, 0, m, dp);// 在剩余len堆中拿到最大
	}

	private int stoneGameII(int[] pre, int index, int m, Integer[][] dp) {
		if (dp[index][m] != null)
			return dp[index][m];
		int rest = pre.length - 1 - index;
		if (2 * m >= rest) {
			return pre[pre.length - 1] - pre[index];
		}
		int max = Integer.MIN_VALUE;
		int range = m * 2;
		for (int x = 1; x <= range; x++) {///// ???? 注意相互依赖
			if (x <= rest) {
				int takeTo = x + index;
				// int takeNum = pre[takeTo] - pre[index];
				int newm = Math.max(x, m);/// ????
				int takeNum1 = stoneGameII(pre, takeTo, newm, dp);/// ?
				// pre[pre.length - 1] - pre[takeTo] - takeNum1 + pre[takeTo] - pre[index];
				max = Math.max(max, pre[pre.length - 1] - pre[index] - takeNum1);
			}
		}
		dp[index][m] = max;
		return max;
	}

	public int f(int[] piles, int l, int r) {
		if (l == r)
			return piles[l];
		int max = piles[l] + s(piles, l + 1, r);
		max = Math.max(max, piles[r] + s(piles, l, r - 1));
		return max;
	}

	public int s(int[] piles, int l, int r) {
		if (l == r)
			return 0;
		int min = f(piles, l + 1, r);
		min = Math.min(min, f(piles, l, r - 1));
		return min;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
		so.debug2();

	}

}
